package datastructure.book.dp._2_linear_pre_section.single.all;

import org.junit.jupiter.api.Test;

import java.util.Arrays;

public class _7_Solution {

    @Test
    public void test(){
        int[][] matrix = {
                { 1, 0,3,-1, 6},
                {-5,-2,3, 4,-6},
                { 4,-9,6, 7, 9},
                { 1, 7,8,-9, 0},
        };
        System.out.println(Arrays.toString(getMaxMatrix(matrix)));
    }

    public int[] getMaxMatrix(int[][] matrix) {
        int max = matrix[0][0];
        int[] result = {0,0,0,0};
        for (int i = 0; i < matrix.length; i++) {
            int tempMax = matrix[i][0];
            int leftIndex = 0;int rightIndex = 0;
            int downIndex = i;
            int[] sum = new int[matrix[i].length];
            for (int m = i; m < matrix.length; m++) {
                sum[0] = sum[0]+matrix[m][0];
                int preDp = sum[0];
                int tempLeftIndex = 0;int tempRightIndex = 0;
                for (int n = 1; n < matrix[i].length; n++) {
                    sum[n] = sum[n]+matrix[m][n];
                    if (preDp > 0) {
                        preDp = preDp + sum[n];
                        tempRightIndex = n;
                    } else {
                        preDp = sum[n];
                        tempLeftIndex = n;
                        tempRightIndex = n;
                    }
                    if (tempMax < preDp) {
                        leftIndex = tempLeftIndex;
                        rightIndex = tempRightIndex;
                        downIndex = m;
                        tempMax = preDp;
                    }
                }
            }
            if (tempMax > max) {
                result[0] = i;result[1] = leftIndex;
                result[2] = downIndex;result[3] = rightIndex;
                max = tempMax;
            }
        }
        return result;
    }
}
